import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author yu
 * @date 2025年06月02日 17:52
 * 216. 组合总和 III
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 * 只使用数字1到9
 * 每个数字 最多使用一次
 *
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 */
public class _07_backtracking_03_216 {
    // 存储所有有效组合
    private static List<List<Integer>> result = new ArrayList<>();
    // 存储当前组合路径
    private static LinkedList<Integer> path = new LinkedList<>();

    /**
     * 查找所有和为n的k个数的组合
     * @param k 要选择的数字个数
     * @param n 目标和
     * @return 所有符合条件的组合列表
     */
    public static List<List<Integer>> combinationSum3(int k, int n) {
        result.clear(); // 清空结果集，避免多次调用时数据残留
        path.clear();   // 清空路径，避免多次调用时数据残留
        backTracking(n, k, 1, 0);
        return result;
    }

    /**
     * 回溯算法核心逻辑
     * @param targetSum 目标和
     * @param k 需要选择的数字个数
     * @param startIndex 开始搜索的数字
     * @param sum 当前组合的和
     */
    public static void backTracking(int targetSum, int k, int startIndex, int sum) {
        // 剪枝 (当前和已超过目标和，直接返回)
        if (sum > targetSum) {
            return;
        }

        // 终止条件：已选满k个数字 且 和等于目标和
        if (path.size() == k) {
            if (sum == targetSum)
                result.add(new ArrayList<>(path));
            return;
        }

        /**
         * 剪枝优化：计算剩余需要选择的数字的最小可能起始值
         *  9 - (k - path.size()) + 1
         */
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);// 处理节点
            sum += i;// 处理节点
            backTracking(targetSum, k, i + 1, sum);
            path.removeLast(); // 回溯
            sum -= i;// 回溯
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        try {
            System.out.print("请输入k值（需要选择的数字个数）：");
            int k = scanner.nextInt();

            System.out.print("请输入n值（目标和）：");
            int n = scanner.nextInt();

            if (k <= 0 || n <= 0) {
                System.out.println("k和n必须为正整数！");
                return;
            }

            List<List<Integer>> combinations = combinationSum3(k, n);

            // 输出结果
            System.out.println("所有和为 " + n + " 的 " + k + " 个数的组合：");
            if (combinations.isEmpty()) {
                System.out.println("没有找到符合条件的组合。");
            } else {
                for (List<Integer> combo : combinations) {
                    System.out.println(combo);
                }
            }
        } catch (Exception e) {
            System.out.println("输入有误，请检查输入格式：" + e.getMessage());
        } finally {
            scanner.close();
        }
    }

}
